package com.algorithm.ch1.cjm.sort;

/**
 * 第一个错误的版本
 * 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
 * 由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 * <p>
 * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 * <p>
 * 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
 * 实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 */
public class FirstBadVersion {

    public static void main(String[] args) {

        System.out.println(new FirstBadVersion().firstBadVersion(2126753390));
    }

    /**
     * 第一个坏版本
     *
     * @param n
     * @return
     */
    public int firstBadVersion(int n) {

        if (n < 1) {
            return 0;
        }

        return middleVersion(1, n);
    }

    /**
     * 二分法
     * 减少对是否为坏版本的调用
     * @param start
     * @param end
     * @return
     */
    int middleVersion(int start, int end) {

        if (start >= end) {
            return start;
        }

        int length = end - start + 1;

        if(length == 2){
            return isBadVersion(start) ? start : end;
        }

        int middle = (end - start) / 2 + start;

        boolean f = isBadVersion(middle);

        if (f) {
            return middleVersion(start, middle);
        } else {
            return middleVersion(middle + 1, end);
        }
    }

    /**
     * 判断是否为坏版本
     *
     * @param version
     * @return
     */
    boolean isBadVersion(int version) {

        if (version >= 1702766719) {
            return true;
        }
        return false;
    }
}
